#define _CRT_SECURE_NO_WARNINGS
#include "stdio.h"
#include "stdlib.h"

typedef int ElemType;

typedef struct LNode {
	ElemType data;  //存储数据
	struct LNode* next;  //存储下一个结点的地址
}LNode, *LinkList;  //指针用于分配内存

//动态创建链表
void CreateList_L(LinkList& L, int n) {
	//创建头结点
	L = (LinkList)malloc(sizeof(LNode));
	L->next = NULL;  //头结点的next为NULL
	for (int i = 0; i < n; i++) {  //遍历存入输入
		LinkList P = (LinkList)malloc(sizeof(LNode));  //创建新节点P
		scanf("%d", & P->data);  //输入P的数据
		P->next = L->next;  //P的next为L的next
		L->next = P;  //头结点L的next指向新结点
	}
}

//查找元素
bool GetElem_L(LinkList L, int i, ElemType &e) {
	//定义一个指针指向头结点
	LinkList P = L;
	int j = 1;
	while (P && j < i) {  //如果P不为空且查找P指向下标不为n
		P = P->next;  //P指向下一个结点
		j++;
	}
	if (!P || j > i) return false;  //如果上面遍历结束P为空（n超出范围）或者查找超出指定范围则返回false
	e = P->data;  //否则返回P指向i结点的数据
	return true;
}

//插入结点
bool ListInsert_L(LinkList L, int i, ElemType e) {
	//定义指针P指向第一个结点
	LinkList P = L;
	int j = 1;
	while (P && j < i-1) {  //在P不为空的情况下遍历n-2次
		P = P->next;  //最终P指向i-1位置的结点
		j++;
	}
	if (!P || j > i) return false;  //不符合条件，插入失败
	LinkList S = (LinkList)malloc(sizeof(LNode));  //为新节点分配空间
	S->data = e;  //为新节点赋data值
	//将结点S接入到链表中
	S->next = P->next;  
	P->next = S;
	return true;
}

//删除结点
void ListDelete_L(LinkList& L, int i, ElemType &e) {
	//获取第i-1个结点
	LinkList P = L;
	int j = 1;
	while (P && j < i) {
		P = P->next;
		j++;
	}
	LinkList q = P->next;  //q为删除的结点
	e = q->data;  //把删除的数据拿走
	P->next = q->next;  //结点i-1和结点i+1连接起来
	free(q);  //释放删除节点
}

//输出链表
void Print_L(LinkList L) {
	LinkList P = L->next;  //定义指针P指向第一个元素
	while (P) {  //如果P不为空
		printf("%3d", P->data);  //输出P指向结点的数据
		P = P->next;
	}
	printf("\n");
}

int main() {
	LinkList L;
	ElemType e=0;  //接收查找的元素
	CreateList_L(L, 5);  //创建有序链表
	Print_L(L);  //输出链表
	GetElem_L(L, 4, e);  //获取元素
	printf("第四个元素是%d\n", e);
	ListInsert_L(L, 1, e);  //插入结点
	Print_L(L);
	ListDelete_L(L, 3, e);  //删除结点
	printf("删除的结点为%d\n", e);
	Print_L(L);
	return 0;
}